package cn.idu.ismik

fun main() {
    val index = 20
    println("fib: ${fib(index)}")
    println("fib2: ${fib2(index)}")
    println("fib3: ${fib3(index)}")
    println("fib3_1: ${fib3_1(index)}")
}

fun fib(n: Int): Int {//递归斐波那契
    if (n == 1 || n == 2) return 1
    return fib(n - 1) + fib(n - 2)
}

fun fib2(n: Int): Int {//带备忘录递归斐波那契
    val memo = IntArray(n + 1)
    return helperMethod(memo, n)
}

fun helperMethod(memo: IntArray, n: Int): Int {
    if (n == 1 || n == 2) return 1
    if (memo[n] != 0) return memo[n]
    memo[n] = helperMethod(memo, n - 1) + helperMethod(memo, n - 2)
    return memo[n]
}

fun fib3(n: Int): Int {//dp数据的迭代解法-动态规划
    if (n < 1) return 0
    if (n == 1 || n == 2) return 1
    val dp = IntArray(n + 1)
    dp[1] = 1
    dp[2] = 1
    for (i in 3 until dp.size) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
}


fun fib3_1(n: Int): Int {//dp数据的迭代解法-动态规划-空间复杂度降至O(1)-状态压缩
    if (n < 1) return 0
    if (n == 1 || n == 2) return 1
    var prev = 1
    var curr = 1
    for (i in 3 until n + 1) {
        prev = curr.apply { curr += prev }
    }
    return curr
}

